/*堆排序*/
#include <stdio.h>
#include "public.h"

int main(){

    //定义无序数组
	int arr[] = {5,6,9,1,3,2,7,8,4,0};
    //获取数组长度
    int len = sizeof(arr)/4;

    //构建循环条件
    while(len>1){

        //构建大顶堆 len/2 - 1 为第一个非叶子节点
        for(int i = len/2 -1; i >= 0; i--){

            //取叶子节点中的最大值 i * 2 + 1 为左叶子，+2为右叶子
            int k = i*2+1;
            if( k+1 < len && arr[k] < arr[k+1]){
                k++;
            }

            //如果叶子节点大于父节点，则进行交换
            if(arr[i] < arr[k]){
                swap(arr,i,k);
            }

        }

        //将大顶堆的根节点放到队尾,并缩短构建顶堆的长度
        swap(arr,0,--len);
    }

    //遍历排序后数组
    len = sizeof(arr)/4;
    each(arr,len);
}